//
// Created by Martin on 2022/4/9.
//

#include <iostream>
#include <stack>

using namespace std;

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int backspace1 = 0;
        int backspace2 = 0;
        int i = s.size() - 1, j = t.size() - 1;
        while (1) {
            while (i >= 0) {
                if (s[i] == '#') backspace1++;
                else {
                    if (backspace1 > 0) backspace1--;
                    else break;
                }
                i--;
            }

            while (j >= 0) {
                if (t[j] == '#') backspace2++;
                else {
                    if (backspace2 > 0) backspace2--;
                    else break;
                }
                j--;
            }

            // 后半部# 消除完, 接下来比较s[i], t[j]
            if (i < 0 || j < 0) break; // s / t遍历到开头了
            if (s[i] != t[j]) return false;
            i--; j--;
        }

        // s和t同时遍历完毕
        if (i == -1 && j == -1) return true;
        return false;
    }
};

int main()
{
    string s1 = "xywrrmp";
    string s2 = "xywrrmu#p";

    Solution s;
    bool res = s.backspaceCompare(s1, s2);
    cout << res << endl;
    return 0;
}
